package com.yuan.algorithms.arithmetic_2;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author YouYuan E-mail:1265161633@qq.com
 * @version 创建时间：2015年7月29日 下午3:21:01 说明:根据中缀表达式利用堆栈建立后缀表达式并求表达式的结果
 */
public class 堆栈_中缀表达式求值 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Character> operator = new Stack<Character>();
		Stack<Double> num = new Stack<Double>();
		while (sc.hasNext()) {
			String str = sc.next();
			disposeExpression(operator, num, str);// 处理表达式
			double result = operation(operator, num);
			System.out.println(result);

		}
	}

	/**
	 * 根据表达式字符串提取运算符和参数并建立后缀表达式
	 * 
	 * @param operator
	 * @param num
	 * @param str
	 */
	private static void disposeExpression(Stack<Character> operator,
			Stack<Double> num, String str) {
		String temp = "";
		for (int i = 0, len = str.length(); i < len; i++) {
			char t = str.charAt(i);
			if ((t >= '0' && t <= '9') || t=='.') {
				temp += t;
				if (i == len-1) {
					if (temp.length() != 0) {
						num.push(Double.parseDouble(temp));
						temp = "";
					}
				}
			} else {
				if (temp.length() != 0) {
					num.push(Double.parseDouble(temp));
					temp = "";
				}
				if (operator.isEmpty()) {
					operator.push(t);
					continue;
				}
				if (t == '+' || t == '-' || t == '*' || t == '/') {
					while (!operator.isEmpty()) {
						char s = operator.peek();
						if (getPriority(s) > getPriority(t)) {
							operator.push(t);
							break;
						} else {
							count(operator, num);
						}
					}
					if (operator.isEmpty()) {
						operator.push(t);
					}
				} else if (t=='(') {
					operator.push(t);
				} else if(t==')'){
					while(operator.peek()!='(') {
						count(operator, num);
					}
					operator.pop();
				}
			}
		}
	}

	/**
	 * 取符号栈的一个元素进行一次运算并将结果加入参数栈
	 * @param operator
	 * @param num
	 */
	private static void count(Stack<Character> operator, Stack<Double> num) {
		double a, b;
		b = num.pop();
		a = num.pop();
		double rs = 0;
		char s = operator.pop();
		switch (s) {
		case '+':
			rs = a + b;
			break;
		case '-':
			rs = a - b;
			break;
		case '*':
			rs = a * b;
			break;
		case '/':
			rs = a / b;
			break;
		}
		num.push(rs);
	}

	/**
	 * 根据运算符栈和参数栈求表达式的结果
	 * 
	 * @param operator
	 * @param num
	 * @return 表达式的结果
	 */
	private static double operation(Stack<Character> operator, Stack<Double> num) {
		while (!operator.isEmpty()) {
			count(operator, num);
		}
		return num.pop();
	}

	/**
	 * 返回当前运算符的优先级
	 * @param s
	 * @return
	 */
	private static int getPriority(char s) {
		int priority = 2;
		switch (s) {
		case '+':
		case '-':
			priority = 2;
			break;
		case '*':
		case '/':
			priority = 1;
			break;
		case '(':
			priority = 3;
			break;
		}
		return priority;
	}

}
